use std::collections::HashMap;
use super::solution::Solution;
impl Solution {
    pub fn minimum_coins(prices: Vec<i32>) -> i32 {
        let length = prices.len();
        let mut cache = [0].repeat(length+1);
        cache[length-1] = prices[length-1];
        for index in (1..length).rev() {
           let  (mut free_l,mut free_r)=(index,index*2+1);
           if free_r>=length+1{
               free_r=length+1;
           }
            if free_l==free_r{
                free_r+=1;
            }
            cache[index-1]=prices[index-1]+cache[free_l..free_r].iter().min().unwrap();
        }
        cache[0]
    }


}

#[cfg(test)]
mod tests {
    use super::Solution;
    #[test]
    fn test_minimum_coins() {
        assert_eq!(Solution::minimum_coins(vec![1,10,1,1]), 2);
    }
}